package E.哈希表;

import java.util.*;

public class _1365_有多少小于当前数字的数字 {
    public static void main(String[] args) {

        _1365_有多少小于当前数字的数字 test = new _1365_有多少小于当前数字的数字();

        System.out.println(test.smallerNumbersThanCurrent(new int[]{
                8, 1, 2, 2, 3}));
    }

    /**
     * 思路1：直接调用sort排序 对原数组进行遍历 依次给出次数
     *
     * @param nums
     * @return
     */

    public int[] smallerNumbersThanCurrent(int[] nums) {

        int index=0;
        int[] init = new int[nums.length];
        for (int num:nums){
            init[index++] = num;
        }
    //    int[] init = nums;
        Arrays.sort(nums);

        ArrayList<Integer> list = new ArrayList<>();
        for (int num :init){
            for (int i=0;i<nums.length;i++){
                if (num == nums[i]){
                    list.add(i);
                    break;
                }

            }
        }

        return list.stream().mapToInt(Integer::valueOf).toArray();

    }

    /**
     * 题解：计数排序：数组元素的值域是有限的 所以可以建立一个频次数组cnt index就是num【i】 对应的数值是出现的次数
     * 这样既可以使得频次数组的index是升序排的 而且也可用过i联系出结果和原数组的顺序
     * 对于i 比他小的所有数字就是cnt[0.。。i-1]的总和
     */
    public int[] smallerNumbersThanCurrent1(int[] nums) {
        //index存的值域 所以需要101
        int[] cnt = new int[101];
        for (int num:nums){
            cnt[num]++;
        }

        for (int i=1;i<cnt.length;i++){
            cnt[i] += cnt[i-1];
        }

        ArrayList<Integer> list = new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            //b不要忘记元素如果是0
            list.add(nums[i]==0?0:cnt[nums[i]-1]);
        }

        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

}
